package sort;

/**
 * @author zxl
 * @version 1.0
 * @date 2021/12/5 17:40
 * 计数排序（不是基于比较排序）  将原有数组元素出现的个数添加到新的数组中，元素作为新数组的索引
 * 用空间换时间
 */
public class CountingSorting {
    static int[] a = new int[]{54, 3, 5, 2, 11, 56, 32, 43, 12, 25, 76, 90, 31, 67, 45, 76, 53, 87, 21};

    public static void main(String[] args) {
        // 计算最大值
        int max = getMax();
        // 创建新的数组
        int[] array = new int[max + 1];
        for (int i = 0; i < a.length; i++) {
            //将原数组的值作为新数组的索引加入到新的数组
            array[a[i]]++;
        }
        //将新数组记录出现的次数转换成新的数组（替换原来的数组）
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            while (array[i]-- > 0) {
                a[index++] = i;
            }
        }

        for (int i : a) {
            System.out.print(i + " ");
        }

    }

    /**
     * 计算最大值
     *
     * @return
     */
    private static int getMax() {
        int max = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }

}
